/*
Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.
*/

class Solution {
public:
    string intToRoman(int num) {
        string result = "";
        result += roman(num/1000%10, 0, 0, 'M'); 
        result += roman(num/100%10, 'M', 'D', 'C'); 
        result += roman(num/10%10, 'C', 'L', 'X'); 
        result += roman(num%10, 'X', 'V', 'I'); 
        return result;
    }
private:
    string roman(int num, char ten, char five, char one) {
        string str = "";
        if (num == 9) {
            str += one;
            str += ten; 
        } else if (num >= 5) {
            str += five;
            while(num-- > 5) str += one;
        } else if (num == 4) {
            str += one; 
            str += five;
        } else {
            while(num-- > 0) str += one;
        }
        return str;
    }
};
